//
//  ProblemOffer34.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 34. 二叉树中和为某一值的路径
 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 示例:
 给定如下二叉树，以及目标和 target = 22，
               5
              / \
             4   8
            /   / \
           11  13  4
          /  \    / \
         7    2  5   1
 返回:
 [
    [5,4,11,2],
    [5,8,4,5]
 ]

 提示：节点总数 <= 10000
 */
@objcMembers class ProblemOffer34: NSObject {
    func solution() {
        let root = TreeNode(5)
        root.left = TreeNode(4)
        root.left?.left = TreeNode(11)
        root.left?.left?.left = TreeNode(7)
        root.left?.left?.right = TreeNode(2)
        
        root.right = TreeNode(8)
        root.right?.left = TreeNode(13)
        root.right?.right = TreeNode(4)
        root.right?.right?.left = TreeNode(5)
        root.right?.right?.right = TreeNode(1)
        
        print(pathSum(root, 22))
    }
    
    func pathSum(_ root: TreeNode?, _ target: Int) -> [[Int]] {
        if root == nil {
            return []
        }
        
        pathSumBFS(root, target)
        return result
    }
    
    // 深度遍历搜索：递归
    var result:[[Int]] = []
    func pathSumDFS(_ root: TreeNode?, _ target: Int, _ list: [Int]) {
        if root == nil {
            return
        }
        
        if root?.left == nil && root?.right == nil {        // 叶子节点
            if root!.val == target {
                var mList = list
                mList.append(root!.val)
                result.append(mList)
            }
            return
        }
        
        var mList = list
        mList.append(root!.val)
        pathSumDFS(root?.left, target-root!.val, mList)
        pathSumDFS(root?.right, target-root!.val, mList)
    }
    
    // 优化
    var mList: [Int] = []
    func pathSumBFS(_ root: TreeNode?, _ target: Int) {
        if root == nil {
            return
        }
        
        mList.append(root!.val)
        if root?.left == nil && root?.right == nil && target == root?.val {        // 叶子节点
            result.append(mList)
        }
        
        pathSumBFS(root?.left, target-root!.val)
        pathSumBFS(root?.right, target-root!.val)
        mList.removeLast()
    }
}
